package leetcode.dp;

import java.util.Arrays;

// 300. 最长递增子序列
public class LengthOfLIS {
    public static void main(String[] args) {
        int[] data = {1,2,3,4,5};
        System.out.println(lengthOfLIS(data));
    }

    // 二分查找+dp
    public static int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] f = new int[n];
        int res = 0;
        for (int num : nums) {
            int low = 0;
            int high = res;
            while (low < high) {
                int mid = low + (high - low) / 2;
                if (f[mid] < num) {
                    low = mid + 1;
                } else {
                    high = mid;
                }
            }
            f[low] = num;
            if (res == high) {
                res++;
            }
        }
        return res;

    }

    // dp
    public int lengthOfLIS2(int[] nums) {
        int n = nums.length;
        int[] f = new int[n];
        // 初始值设为1
        Arrays.fill(f, 1);
        int res = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    f[i] = Math.max(f[i], f[j] + 1);
                }
            }
            res = Math.max(res, f[i]);
        }
        return res;
    }
}
